import java.util.Scanner;

public class J20250405 {

//五、递归
    //递归的必要条件：
    //1. 将原问题划分成其⼦问题，注意：⼦问题必须要与原问题的解法相同
    //2. 递归出⼝
    //3. 要有结束条件
    //4. 关于"调⽤栈"
    //   ⽅法调⽤的时候,会有⼀个"栈"这样的内存空间描述当前的调⽤关系.称为调⽤栈.
    //   每⼀次的⽅法调⽤就称为⼀个"栈帧",每个栈帧中包含了这次调⽤的参数是哪些,返回到哪⾥继续执⾏等信息.



    //求N！

    public static void main1(String[] args) {
        int n = 5;
        int ret = factor(n);
        System.out.println("ret = " + ret);
    }
    public static int factor (int n){
        if (n == 1){
            return 1;
        }
        return n * factor(n -1);   // factor调用函数自身
    }




    //递归求N的阶乘

    public static void main2(String[] args) {
        int n = 5;
        int ret = factor2(n); //调用factor2方法计算n的阶乘，并将结果存储在变量ret中
        System.out.println("ret = " + ret);
    }
    public static int factor2(int n){
        System.out.println("函数开始， n = " + n);
        //递归结束条件
        if (n == 1){
            System.out.println("函数结束， n = 1 ret = 1");
            return 1;
        }
        //如果n不等于1，那么当前的阶乘结果等于n乘以n-1的阶乘。这里通过递归调用factor2(n-1)来计算n-1的阶乘
        int ret = n * factor2(n - 1);
        System.out.println("函数结束， n = " + n + " ret = " + ret);
        return ret;
    }




    //按顺序打印数字的每一位

    //方法1
    public static void print(int n){
        if(n <= 9){
            System.out.println(n);
        } else {
            print(n / 10);//得到1234 123 12 1
            System.out.println(n % 10);//1%10得到1、12%10得到2、123%10得到3、1234%10得到4
        }
    }
    public static void main3(String[] args) {
        print(1234);//调用方法print
    }

    //方法2
    public static void print2(int n){
        if(n > 9){
            print(n / 10);//1234>9取1234出来除10得123、123>9除10得12、12>9除10得1、1不大于9执行下一步打印出来
        }
        System.out.println(n % 10);//由上一步打印得到1、取12%10得到2、123除10得到3、1234除10得到4
    }
    public static void main4(String[] args) {
        print2(1234);//调用print2方法
    }




    //递归求1+2+3+4+.....+10

    public static int add(int n){
        if(n == 1){
            return 1;
        }
        return n + add(n - 1);
    }
    public static void main5(String[] args) {
        int n = 10;   //输入实参
        int sum = add(n);   //调用add方法并且将结果存在sum中
        System.out.println(sum);
    }




    //写⼀个递归⽅法，输⼊⼀个⾮负整数，返回组成它的数字之和.

    // 例如，输⼊1729,则应该返回1+7+2+9，它的和是19
    public static int sum(int num){
        if (num < 10){
            return num;
        }
        return num % 10 + sum(num / 10);
    }
    public static void main6(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int result = sum(num);
        System.out.println(result);
    }




    //求斐波那契数列的第N项

    //方法1
    public static int fib(int n){
        if (n == 3){
            count++; //计算执行次数
        }

        if (n == 1 || n == 2){
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    public static int count = 0; //这个是类的成员变量
    public static void main7(String[] args) {
        int n = 40;
        int result = fib(n);
        System.out.println(result);
        System.out.println("次数：" + count);
    }



    //方法2 使⽤循环的⽅式来求斐波那契数列问题,避免出现冗余运算
    public static int fib2(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        int last2 = 1;
        int last1 = 1;
        int cur = 0;
        for(int i = 3; i <= n; i++){
            cur = last1 + last2;
            last2 = last1;
            last1 = cur;
            count++;
        }
        return cur;
    }

    public static void main8(String[] args) {
        int n = 40;
        int result = fib2(n);
        System.out.println(result);
        System.out.println(count);
    }



    //方法3 极限代码(执行次数与第一种一样)
    public static void main(String[] args) {
        System.out.println(fib3(40));
    }

    public static int fib3(int n){
        if(n == 1 || n == 2){
            return 1;
        }else{
            return fib3(n-1) + fib3(n - 2);
        }
    }





    //汉诺塔
    public static void hanoi(int n, char pos1, char pos2, char pos3){
        if(n != 0){
            sum++; //计算所需要的步骤数
        }
        if (n == 1){
            move(pos1, pos3);
            return;
        }
        hanoi(n-1, pos1, pos3, pos2);
        move(pos1, pos3);
        hanoi(n-1, pos2, pos1, pos3);
    }


    public static void move(char posSrc, char posDest){
        System.out.print(posSrc + "->" + posDest + " ");
    }

    public static int sum =0; //这个类的成员变量
    public static void main19(String[] args) {
        System.out.println("执行次数为：" + sum);
        hanoi(4, 'A', 'B', 'C');
    }



}
